package org.myy.learn.aaa.c_滑动窗口;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

@Slf4j
public class 找到字符串的全部字母异位词_438 {

    //字母、异位词
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        int m = s.length(), n=p.length();
        int[] sArr = new int[26], pArr = new int[26];   //todo 保证数组一致，才能比较
        for (int i=0; i<n; i++){pArr[p.charAt(i)-'a']++;}
        //滑动窗口：right一直往前走，left看情况进一
        for (int left = 0, right = 0; right < m; right++){
            sArr[s.charAt(right) - 'a']++;
            if (right - left + 1 == n){
                boolean flag = Arrays.equals(sArr, pArr);
                if (flag){
                    list.add(left);
                }
                //sArr[left]--;
                sArr[s.charAt(left)-'a']--;             //todo 移除的是s字符串的left，不是数组中的left
                left++;
            }
        }
        return list;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd", p = "abc";
        List<Integer> findAnagrams = findAnagrams(s, p);
        log.info("执行结束, findAnagrams={}", findAnagrams);
    }
}
